// 自顶向下归并
function mergeSort (arr) {
  if (arr == null || arr.length < 2) {
    return
  }
  _sort(arr, 0, arr.length - 1)
}

function _sort (arr, L, R) {
  if (L === R) {
    return
  }
  const mid = L + Math.floor((R - L) / 2)
  _sort(arr, L, mid)
  _sort(arr, mid + 1, R)
  _merge(arr, L, mid, R)
}

function _merge (arr, L, mid, R) {
  const helperArr = new Array(R - L + 1)
  let i = L
  let j = mid + 1
  let index = i - L
  while (i <= mid && j <= R) {
    helperArr[index++] = arr[i] < arr[j] ? arr[i++] : arr[j++]
  }
  while (i <= mid) {
    helperArr[index++] = arr[i++]
  }
  while (j <= R) {
    helperArr[index++] = arr[j++]
  }
  // 往回拷贝
  for (i = 0; i < helperArr.length; i++) {
    arr[i + L] = helperArr[i]
  }
}

// 自底向上归并排序
function mergeSortBU (arr) {
  for (let step = 1; step < arr.length; step *= 2) {
    for (let left = 0; left < arr.length - step; left += 2 * step) {
      _merge(arr, left, left + step - 1, Math.min(left + 2 * step - 1, arr.length - 1))
    }
  }
}

export default { mergeSort, mergeSortBU }
